package com.lun.medium;

import com.lun.util.BinaryTree.TreeNode;

public class CountCompleteTreeNodes {
	
	//方法一：
    private int height(TreeNode root) {
        return root == null ? -1 : 1 + height(root.left);
    }
    
    public int countNodes(TreeNode root) {
        int h = height(root);
        return h < 0 ? 0 :
               height(root.right) == h - 1 ? (1 << h) + countNodes(root.right)
                                         : (1 << h - 1) + countNodes(root.left);
    }
    
    //方法二：稍微修饰方法一
    private int height2(TreeNode root) {
    	return root == null ? 0 : 1 + height2(root.left);
    }
    
    public int countNodes2(TreeNode root) {
    	int h = height2(root);
    	return h == 0 ? 0 :
    		height2(root.right) == h - 1 ? // 
    				(1 << (h - 1)) + countNodes2(root.right) : // 
    				(1 << (h - 2)) + countNodes2(root.left);
    }
    
    //方法三：方法一的迭代版
    public int countNodes3(TreeNode root) {
        int nodes = 0, h = height(root);
        while (root != null) {
            if (height(root.right) == h - 1) {
                nodes += 1 << h;
                root = root.right;
            } else {
                nodes += 1 << h - 1;
                root = root.left;
            }
            h--;
        }
        return nodes;
    }
    
    //方法四：
    public int countNodes4(TreeNode root) {
        if (root == null)
            return 0;
        TreeNode left = root, right = root;
        int height = 0;
        while (right != null) {
            left = left.left;
            right = right.right;
            height++;
        }
        if (left == null)
            return (1 << height) - 1;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
    
    //方法五：方法一的对称写法形式
    public int countNodes5(TreeNode root) {
        if (root == null)
            return 0;
        int lh = height2(root.left);
        int rh = height2(root.right);     
        if(lh == rh) 
           return (1 << lh) + countNodes5(root.right);  /*1(根节点) + (1<<lh)-1(完全左子树) + # of rightNode */               
        else 
           return (1 << rh) + countNodes5(root.left);  /*1(根节点) + (1<<rh)-1(完全右子树) + # of leftNode*/
    }
    
    
}
